package com.tucc.hello.leetcode.no1_400.no1_200.no41_60.no60;

import java.util.LinkedHashMap;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 4;
        int k = 1;
        int total = 1;
        for (int i = 1; i <= n; i++) {
            total *= i;
        }
        for (int kk = 1; kk <= total; kk++) {
            System.out.println(solution.getPermutation(n, kk));
        }
    }

    public String getPermutation(int n, int k) {
        int[] nums = new int[n + 1];
        int total = 1;
        for (int i = 1; i <= n; i++) {
            nums[i] = i;
            total *= i;
        }
        StringBuilder builder = new StringBuilder();
        getPermutation(nums, n, total, k, builder);
        return builder.toString();

    }

    public void getPermutation(int[] nums, int n, int total, int k, StringBuilder builder) {
        if (n <= 0) {
            return;
        }
        if (k == total || k == 0) {
            for (int i = n; i >= 1; i--) {
                builder.append(nums[i]);
            }
        } else if (k == 1) {
            for (int i = 1; i <= n; i++) {
                builder.append(nums[i]);
            }
        } else {
            int nextTotal = total / n;
            int curBatch = (k - 1) / nextTotal + 1;
            int nextK = k % nextTotal;
            int curNum = nums[curBatch];
            for (int i = curBatch; i < n; i++) {
                nums[i] = nums[i + 1];
            }
            nums[n] = curNum;
            builder.append(curNum);
            getPermutation(nums, n - 1, nextTotal, nextK, builder);
        }
    }


}
